// Simple set operations
// Thanks to E.P. Wentworth for useful ideas!
// Corrected and extended version Sun  10-24-99

#ifndef SET_H
#define SET_H

template <int maxElem>              
class Set {                                     // { 0 .. maxElem }
  public:
    Set()                                       // Construct { }
    { clear(); }

    Set(int e1)                                 // Construct { e1 }
    { clear(); incl(e1); }

    Set(int e1, int e2)                         // Construct { e1, e2 }
    { clear(); incl(e1); incl(e2); }

    Set(int e1, int e2, int e3)                 // Construct { e1, e2, e3 }
    { clear(); incl(e1); incl(e2); incl(e3); }

    Set(int e1, int e2, int e3, int e4)         // Construct { e1, e2, e3, e4 }
    { clear(); incl(e1); incl(e2); incl(e3); incl(e4); }

    Set(int e1, int e2, int e3, int e4, int e5) // Construct { e1, e2, e3, e4, e5 }
    { clear(); incl(e1); incl(e2); incl(e3); incl(e4); incl(e5); }

    Set(int n, int e1[])                        // Construct { e[0] .. e[n-1] }
    { clear(); for (int i = 0; i < n; i++) incl(e1[i]); }

    void fill(void)                             // Include all elements
    { for (int i = 0; i < length; i++) bits[i] = 0xFF; }

    void incl(int e)                            // Include e
    { if (e >= 0 && e <= maxElem) bits[wrd(e)] |= bitmask(e); }

    void excl(int e)                            // Exclude e
    { if (e >= 0 && e <= maxElem) bits[wrd(e)] &= ~bitmask(e); }

    int memb(int e)                             // Test e for membership
    { if (e >= 0 && e <= maxElem) return((bits[wrd(e)] & bitmask(e)) != 0);
      else return 0;
    }

    int isempty(void)                           // Test for empty set
    { for (int i = 0; i < length; i++) if (bits[i]) return 0;
      return 1;
    }

    int members(void)                           // Return number of elements
    { int n = 0;
      for (int i = 0; i < maxElem; i++) if (memb(i)) n++;
      return n;
    }

    Set operator + (const Set &s)               // Union with s
    { Set<maxElem> r;
      for (int i = 0; i < length; i++) r.bits[i] = bits[i] | s.bits[i];
      return r;
    }

    Set operator * (const Set &s)               // Intersection with s
    { Set<maxElem> r;
      for (int i = 0; i < length; i++) r.bits[i] = bits[i] & s.bits[i];
      return r;
    }

    Set operator - (const Set &s)               // Difference with s
    { Set<maxElem> r;
      for (int i = 0; i < length; i++) r.bits[i] = bits[i] & ~s.bits[i];
      return r;
    }

    Set operator / (const Set &s)               // Symmetric difference with s
    { Set<maxElem> r;
      for (int i = 0; i < length; i++) r.bits[i] = bits[i] ^ s.bits[i];
      return r;
    }

  private:
    unsigned char       bits[(maxElem + 8) / 8];
    int                 length;
    int wrd(int i)      { return(i / 8); }
    int bitmask(int i)  { return(1 << (i % 8)); }
    void clear()        { length = (maxElem + 8) / 8;
                          for (int i = 0; i < length; i++) bits[i] = 0;
                        }
};

#endif /* SET_H */
